#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2021, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 0001.py
@time: 2021/9/6 20:20
@desc:
'''


class Solution:
    def search(self, nums: list, target: int) -> int:
        mid = len(nums) // 2
        if mid == 0:
            if nums[mid]==target:
                return mid
            else:
                return -1
        if target < nums[mid]:
            m = self.search(nums[:mid], target)
            if m == -1:
                return m
            return m

        elif target > nums[mid]:
            m = self.search(nums[mid:], target)
            if m == -1:
                return m
            return mid + m
        else:
            return mid

class Solution02:
    def search(self, nums: list, target: int) -> int:
        left, right = 0, len(nums)-1
        while left <= right:
            mid = (left + right) // 2
            if target == nums[mid]:
                return mid
            elif target < nums[mid]:
                right = mid - 1
            elif target > nums[mid]:
                left = mid + 1

        return -1

if __name__ == '__main__':
    # nums = [5]
    # solution = Solution()
    # mid = solution.search(nums, 5)
    nums = [-1,0,3,5,9,12]
    target = 9
    s = Solution02()
    mid = s.search(nums, target)
    print(mid)

